package com.hy.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum2 {

    /**
     * 第18题. 四数之和
     * 力扣题目链接
     *
     * 题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
     *
     * 注意：
     * 答案中不可以包含重复的四元组。
     * 示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
     * 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
     *
     * 四数之和，和15.三数之和是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。
     *
     * 但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，
     * 因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，
     * 不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。
     *
     * 而454.四数相加II是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！
     */
    // 双指针法
    public static List<List<Integer>> fourSum2(int [] num,int target){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(num);
        for (int i = 0; i < num.length; i++) {
            // 去重
            if (i> 0 && num[i - 1] == num[i] ){
                continue;
            }

            for (int j = i+1; j < num.length; j++) {
                // 去重
                if (j > i+1 && num[j -1] == num[j]){
                    continue;
                }

                // 定义 快慢指针
                int left = j + 1;
                int right = num.length -1;

                while (right > left){
                    int sum = num[i] + num[j] + num[left] +num[right];
                    // 当前元素不合适了，可以去重
                    if (sum > target){
                        right --;
                    }else if (sum < target){
                        left ++;
                    }else {
                        res.add(Arrays.asList(num[i],num[j],num[left],num[right]));
                        // 去重
                        while (right > left && num[right]  == num[right-1] ) {
                            right --;
                        }
                        while (right > left && num[left] == num[left +1]){
                            left ++;
                        }
                        // 找到答案时，双指针同时收缩
                        right --;
                        left ++;
                    }

                }


            }
            
        }
        return res;

    }

    public static void main(String[] args) {
        int [] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        System.out.println(fourSum2(nums,target));
    }
}
